package com.sunny.example;

import java.util.Scanner;

/**
 * 购物单
 * 描述
 * 王强决定把年终奖用于购物，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子：
 * 主件 	附件
 * 电脑 	打印机，扫描仪
 * 书柜 	图书
 * 书桌 	台灯，文具
 * 工作椅 	无
 * 如果要买归类为附件的物品，必须先买该附件所属的主件，且每件物品只能购买一次。
 * 每个主件可以有 0 个、 1 个或 2 个附件。附件不再有从属于自己的附件。
 * 王强查到了每件物品的价格（都是 10 元的整数倍），而他只有 N 元的预算。除此之外，他给每件物品规定了一个重要度，用整数 1 ~ 5 表示。他希望在花费不超过 N 元的前提下，使自己的满意度达到最大。
 * 满意度是指所购买的每件物品的价格与重要度的乘积的总和，假设设第iii件物品的价格为v[i]v[i]v[i]，重要度为w[i]w[i]w[i]，共选中了kkk件物品，编号依次为j1,j2,...,jkj_1,j_2,...,j_kj1​,j2​,...,jk​，则满意度为：v[j1]∗w[j1]+v[j2]∗w[j2]+…+v[jk]∗w[jk]v[j_1]*w[j_1]+v[j_2]*w[j_2]+ … +v[j_k]*w[j_k]v[j1​]∗w[j1​]+v[j2​]∗w[j2​]+…+v[jk​]∗w[jk​]。（其中 * 为乘号）
 * 请你帮助王强计算可获得的最大的满意度。
 * <p>
 * <p>
 * <p>
 * 输入描述：
 * <p>
 * 输入的第 1 行，为两个正整数N，m，用一个空格隔开：
 * （其中 N （ N<32000 ）表示总钱数， m （m <60 ）为可购买的物品的个数。）
 * <p>
 * <p>
 * 从第 2 行到第 m+1 行，第 j 行给出了编号为 j-1 的物品的基本数据，每行有 3 个非负整数 v p q
 * <p>
 * <p>
 * （其中 v 表示该物品的价格（ v<10000 ）， p 表示该物品的重要度（ 1 ~ 5 ）， q 表示该物品是主件还是附件。如果 q=0 ，表示该物品为主件，如果 q>0 ，表示该物品为附件， q 是所属主件的编号）
 * <p>
 * <p>
 * <p>
 * <p>
 * 输出描述：
 * 输出一个正整数，为张强可以获得的最大的满意度。
 */
public class HJ16 {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int totalMoney = scanner.nextInt();//总钱数
        int goodsNum = scanner.nextInt();//期望购买的总物品数

        Goods[] goods = new Goods[goodsNum];
        //初始化Goods对象
        for (int i = 0; i < goodsNum; i++) {
            goods[i] = new Goods();
        }

        for (int i = 0; i < goodsNum; i++) {
            int price = scanner.nextInt();//价钱
            int level = scanner.nextInt();//重要级别
            int tag = scanner.nextInt();//是否为主件的一个标记

            goods[i].unitPrice = price;
            goods[i].rate = price * level;
            if (tag == 0) {
                //当前为主件
                goods[i].isMain = true;
            } else {
                //当前为附件，得查找它的主件
                //因为tag是从1开始的，所以数组的index需要-1
                if (goods[tag - 1].subGood1 == -1) {
                    //一个主件最多只能有2个附件，因此如果已经存在附件1，则tag还>0,则说明是第二个附件
                    goods[tag - 1].subGood1 = i;
                } else {
                    goods[tag - 1].subGood2 = i;
                }
            }
        }

        //接下来计算满意度
        int[] dp = new int[totalMoney + 1];
        for (int i = 1; i <= goodsNum; i++) {//商品从1开始算起
            for (int j = totalMoney; j >= 0; j--) {
                //因为买附件要得先买主件，上面已经将主件，附件通过Goods对象关联起来了
                //过滤掉附件
                if (!goods[i - 1].isMain) {
                    continue;
                }

                int curPrice = goods[i - 1].unitPrice;//当前商品价格
                if (j >= curPrice) {
                    dp[j] = Math.max(dp[j], dp[j - curPrice] + goods[i - 1].rate);
                }
                int subGoodId1 = goods[i - 1].subGood1;//附件1
                int subGoodId2 = goods[i - 1].subGood2;//附件2
                if (subGoodId1 != -1) {
                    //当只有附件1时，附件1对应的主件 + 附件1
                    int subGood1Price = goods[subGoodId1].unitPrice;//附件1价钱
                    if (j >= (subGood1Price + curPrice)) {
                        dp[j] = Math.max(dp[j], dp[j - curPrice - subGood1Price] + goods[i - 1].rate + goods[subGoodId1].rate);
                    }
                } else if (subGoodId2 != -1) { //有附件2
                    int subGood2Price = goods[subGoodId2].unitPrice;//附件2的价钱
                    if (j >= (subGood2Price + curPrice)) {
                        dp[j] = Math.max(dp[j], dp[j - curPrice - subGood2Price] + goods[i - 1].rate + goods[subGoodId2].rate);
                    }
                } else if (subGoodId1 != -1 && subGoodId2 != -1) {
                    //同时有附件1，附件2
                    int subGood1Price = goods[subGoodId1].unitPrice;
                    int subGood2Price = goods[subGoodId2].unitPrice;
                    dp[j] = Math.max(dp[j], dp[j - curPrice - subGood1Price - subGood2Price]
                            + goods[i - 1].rate + goods[subGoodId1].rate + goods[subGoodId2].rate);
                }
            }

        }

        System.out.println(dp[totalMoney]);
    }

    static class Goods {
        int unitPrice;//单价
        int rate;//满意度
        boolean isMain;//是否为主件
        int subGood1, subGood2 = -1;//附件1，附件2：（一个主件最多可以有2个附件）
    }
}


